124

11

Randomness and Complexity

of heads or tails is 0.5. We cannot assess the randomness of a single result, but we

can assess the probability that a sequence of tosses is random. So perhaps we can

answer the question of whether a given individual sequence is random. The three

main notions of randomness are as follows: ²

1. Stochasticity, or frequency stability, associated with von Mises, Wald, and

Church; ³

2. Incompressibility or chaoticity, associated with Solomonoff, Kolmogorov, and

Chaitin; ⁴

3. Typicality, associated with Martin-Löf (and essentially coincident with incom-

pressibility).

11.1

Random Processes

A process characterized by a succession of values of a characteristic parameter yy is

called random ifyy does not depend in a completely definite way on the independent

variable, usually (laboratory) timett, but in the context of sequences, the independent

variable could be the position along the sequence. A random process is therefore

essentially different from a causal process (cf. Sect. 9.1). It can be completely defined

by the set of probability distributions upper W 1 left parenthesis y t right parenthesis d yW1(yt)dy, the probability of finding yy in the

range left parenthesis y comma y plus(y, y + dy right parenthesisy) at time tt, upper W 2 left parenthesis y 1 t 1 comma y 2 t 2 right parenthesisW2(y1t1, y2t2) dy 1y1 dy 2y2, the joint probability of finding yy

in the rangeleft parenthesis y 1 comma y 1 plus(y1, y1 + dy 1 right parenthesisy1) at timet 1t1 and in the rangeleft parenthesis y 2 comma y 2 plus(y2, y2 + dy 2 right parenthesisy2) at timet 2t2, and so

forth for triplets, quadruplets, ellipsis. . . of values of yy.

If there is an unchanging underlying mechanism, the probabilities are stationary

and the distributions can be simplified as upper W 1 left parenthesis y right parenthesis d yW1(y)dy, the probability of finding yy in

the range left parenthesis y comma y plus(y, y + dy right parenthesisy); upper W 2 left parenthesis y 1 y 2 t right parenthesisW2(y1y2t) dy 1y1 dy 2y2, the joint probability of finding yy in the

ranges left parenthesis y 1 comma y 1 plus(y1, y1 + dy 1 right parenthesisy1) and left parenthesis y 2 comma y 2 plus(y2, y2 + dy 2 right parenthesisy2) separated by an interval of time t equals t 2 minus t 1t = t2 −t1;

and so on. Experimentally, a single long record y left parenthesis t right parenthesisy(t) can be cut into pieces (which

should be longer than the longest period supposed to exist), rather than carrying

out measurements on many similarly prepared systems. This equivalence of time

2 After Volchan (2002).

3 Von Mises called the random sequences in accord with this notion “collectives”. It was subse-

quently shown that the collectives were not random enough (see Volchan (2002) for more details); for

example, the number0.0123456789101112131415161718192021 ellipsis0.0123456789101112131415161718192021 . . . satisfied von Mises’ criteria

but is clearly computable.

4 The Kolmogorov–Chaitin definition of the descriptive or algorithmic complexityupper K left parenthesis s right parenthesisK(s) of a sym-

bolic sequencess with respect to a machineupper MM running a program P is given by

K(s) =

{ ∞

if there is no P such that M (P) = s

min{|P| : M (P) = s} otherwise .

(11.1)

This means that upper K left parenthesis s right parenthesisK(s) is the size of the smallest input program P that prints ss and then stops

when input intoupper MM . In other words, it is the length of the shortest (binary) program that describes

(codifies) ss. Insofar as upper MM is usually taken to be a universal Turing machine, the definition is

machine-independent.